#include<iostream>
#include<vector>
using namespace std;
//dp O(N^2)
class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<bool>dp(nums.size(),false);
        dp[0]=true;
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&nums[j]>=i-j){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp.back();
    }
};
//贪心
class Solution {
public:
    bool canJump(vector<int>& nums) {
        //从0能跳到的最远距离
        int fast_des=0;
        for(int i=0;i<nums.size();i++){
            //不能跳到这个点 失败
            if(i>fast_des)return false;
            //能挑到这个点 更新最远距离
            fast_des=max(fast_des,i+nums[i]);
        }
        //所有点都能跳到 成功
        return true;
    }
};